Problem Link

https://leetcode.com/problems/product-of-array-except-self/

How to solve

Suppose we have a number i. Notice that the product of all numbers except i is equal to the product of all numbers to the left of i multiplied by the product of all numbers to the right of i. For example, let the array nums = [1,2,3,4]. For every number i, calculate the product of all numbers to the left of i. We have the array:

L = [1, 1, 2, 6]

To calculate the product of all numbers to the right of i, we don't need to create another array. Instead, we keep a variable R that represents the running-product of all elements to the right of i. Iterating through the array backwards, for every index j, we multiply L[j] by R to get the product of all numbers except nums[j]. We update our running-product R by mulitiplying it by nums[j].

Complexity Analysis

Time: O(N)

We iterate through the nums array twice, which is O(2n) = O(n). First, to create an array L which holds the products of all elements to the left of index i. Second, we iterate through L backwards, updating each index to hold the product of all numbers except nums[i] for all i.

Space: O(1)

Although we create an array of size N to store the products for each number in nums, the problem states that the output array does not count toward our space complexity.

Solutions

Python

def productExceptSelf(self, nums: List[int]) -> List[int]:
    L = [1 for _ in range(len(nums))]

    for i in range(1, len(nums)):
        L[i] = nums[i - 1] * L[i - 1]

    ans = L
    R = 1
    for j in range(len(nums) - 1, -1, -1):
        ans[j] *= R
        R *= nums[j]

    return ans

Go

Using C-style for-loop

func productExceptSelf(nums []int) []int {
    L := make([]int, len(nums))
    L[0] = 1

    for j := 1; j < len(nums); j++ {
        L[j] = nums[j - 1] * L[j - 1]
    }

    ans := L
    R := 1
    for k := len(nums) - 1; k > -1; k-- {
        ans[k] *= R
        R *= nums[k]
    }

    return ans
}

Using range loop

func productExceptSelf(nums []int) []int {
    L := make([]int, len(nums))
    L[0] = 1

    for j, num := range nums[0 : len(nums) - 1] {
        L[j + 1] = num * L[j]
    }

    ans := L
    R := 1
    for i, _ := range nums {
        ans[len(nums) - 1 - i] *= R
        R *= nums[len(nums) - 1 - i]
    }

    return ans
}

Rust

pub fn product_except_self(nums: Vec<i32>) -> Vec<i32> {
    let mut L = vec![1; nums.len()];

    for i in 1..nums.len() {
        L[i] = nums[i - 1] * L[i - 1];
    }

    let mut ans = L;
    let mut R = 1;
    for j in (0..nums.len()).rev() {
        ans[j] *= R;
        R *= nums[j];
    }

    ans
}